package demo150;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class GetLeastNumbers_Solution {
    public static void main(String[] args) {
        int[] s=  new int[]{1,8,9,7,5,7,2,3,6,4};
        ArrayList<Integer> ret = GetLeastNumbers_Solution(s,4);
        for(Integer x : ret) {
            System.out.println(x);
        }
    }

    public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> ret  = new ArrayList<>();

        if(k == 0 || input.length == 0) {
            return ret;
        }

        //大根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(
                (o1,o2)->o2.compareTo(o1));

        for(int i = 0;i < k;i++) {
            queue.offer(input[i]);
        }
        for(int i = k;i < input.length;i++) {
            //较小的元素入堆
            if(queue.peek() > input[i]) {
                queue.poll();
                queue.offer(input[i]);
            }
        }


        for(int i = 0;i < k;i++) {
            ret.add(queue.poll());
        }


        return ret;
    }


    public ArrayList<Integer> GetLeastNumbers_Solution1 (int[] input, int k) {
        // write code here
        Arrays.sort(input);
        ArrayList<Integer> ret  = new ArrayList<>();
        for(int i = 0;i < k;i++) {
            ret.add(input[i]);
        }


        return ret;
    }
}
